State machines are a fundamental part of much electronic equipment. An example of a very simple state machine is shown in FIG. 1. This state machine has four states S1 10, S2 12, S3 14, S4 16. Also shown are various possible transitions between states. These include transition 18 between S1 10 and S2 12; transition 20 between S2 12 and S4 16, transition 22 between S4 16 and S3 14; transition 24 between S2 12 and S3 14, and finally transition 26 between S3 14 and S1 10. At each iteration of the state machine, the current state, be that either S1, S2, S3 or S4, and a current input which might take the form of several bits, are processed and a new “next state” is determined. The possible next states are represented by the transitions in FIG. 1. Such a state computation might also determine an output that is produced at the particular state transition. For example, when a transition from state S1 10 to S2 12 occurs, three bits of output might be generated at that time.
State machines have been implemented with mechanical devices, electronic hardware and software techniques. Most software programming of state machines is done now using high level object oriented techniques that can be very slow.
An example of a Mealy hardware implementation of a state machine is shown in FIG. 2. In this example, input bits 30 and a current state 34 are input to combinatorial logic 32. Combinatorial logic 32 determines the next state 36 on the basis of the input bits 30 and the current state 34. The next state is then stored using a flip flop 38 and that state now becomes the current state 34 for use in the next iteration. Additional combinatorial logic 40 takes the input bits 30 and the current state 34 and determines any output 42. There are well known techniques for determining appropriate combinatorial logic 32 to implement a particular state machine.